package mws;//给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
//
//
//
// 示例 1:
//
//
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
//
// 示例 2:
//
//
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
//
// 示例 3:
//
//
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 5 * 10⁴
// s 由英文字母、数字、符号和空格组成
//
//
// Related Topics 哈希表 字符串 滑动窗口 👍 11025 👎 0


import java.util.ArrayList;
import java.util.HashSet;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring("c"));
    }
    private HashSet<Character> set = new HashSet<>();
    public int lengthOfLongestSubstring(String s) {
        ArrayList<Character> list = new ArrayList<>();
        int count = 0;
        for (int right = 0; right < s.length(); right++) {

            Character c = s.charAt(right);
            if(set.contains(c)){
                count = Math.max(count, list.size());
                while (true){
                    Character c1 = list.removeFirst();
                    if(c.equals(c1)){
                        break;
                    }
                    set.remove(c1);
                }
            }else {
                set.add(c);
            }
            list.add(c);
        }
        count = Math.max(count, list.size());
       // tree(s,0);
        return count;

    }
    public int maxLength = 0;
    public void tree(String s,int n){
        /**
         * 结果return
         */
        if(n > s.length()) {
            maxLength = Math.max(maxLength, set.size());
            return;
        }

        /**
         * 备忘录return
         */


        /**
         * 筛选（进入下一个）递归
         */
        for (int i = n; i < s.length(); i++) {
            char c = s.charAt(i);
            if(set.contains(c)){
                maxLength = Math.max(maxLength, set.size());
                return;
            }else {
                set.add(c);
                tree(s,n+1);
                set.remove(s.charAt(i));
            }
        }

        /**
         * （记录备忘录）
         */


        /**
         * 无结果return
         */
        return;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
